#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

// Definition for a binary tree node
struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {};
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {};
};

class Solution
{
public:
	// Inorder DFS helper
	void inorder_dfs(TreeNode *root, vector<int> &arr)
	{
		if (!root)
			return;
		inorder_dfs(root->left, arr);
		arr.push_back(root->val);
		inorder_dfs(root->right, arr);
	}

	// 94. Inorder traversal
	vector<int> inorderTraversal(TreeNode *root)
	{
		vector<int> arr;
		if (!root)
			return arr;

		inorder_dfs(root, arr);
		return arr;
	}

	// 100. Check if two trees are the same
	bool isSameTree(TreeNode *p, TreeNode *q)
	{
		if (!p && !q)
			return true;
		if ((!p && q) || (p && !q))
			return false;

		return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
	}

	// Mirror a tree
	TreeNode *reverseTree(TreeNode *root)
	{
		if (!root)
			return NULL;

		TreeNode *cur = reverseTree(root->right);
		root->right = reverseTree(root->left);
		root->left = cur;

		return root;
	}

	// 101. Check if tree is symmetric
	bool isSymmetric(TreeNode *root)
	{
		return isSameTree(root->left, reverseTree(root->right));
	}

	// 104. Maximum depth of tree
	int maxDepth(TreeNode *root)
	{
		if (!root)
			return 0;
		return max(maxDepth(root->left), maxDepth(root->right)) + 1;
	}

	// Build BST from sorted array
	TreeNode *buildBST(vector<int> &nums, int l, int r)
	{
		if (l > r)
			return NULL;

		int mid = (l + r) / 2;
		TreeNode *root = new TreeNode(nums[mid]);
		root->left = buildBST(nums, l, mid - 1);
		root->right = buildBST(nums, mid + 1, r);
		return root;
	}

	// 108. Convert sorted array to BST
	TreeNode *sortedArrayToBST(vector<int> &nums)
	{
		return buildBST(nums, 0, nums.size() - 1);
	}

	// Get tree height
	int height(TreeNode *root)
	{
		if (!root)
			return 0;
		return max(height(root->left), height(root->right)) + 1;
	}

	// 110. Check if tree is balanced
	bool isBalanced(TreeNode *root)
	{
		if (!root)
			return true;
		int left = height(root->left);
		int right = height(root->right);

		if (abs(left - right) > 1)
			return false;
		return isBalanced(root->left) && isBalanced(root->right);
	}

	// 111. Minimum depth of tree
	int minDepth(TreeNode *root)
	{
		if (!root)
			return 0;
		if (!root->left)
			return minDepth(root->right) + 1;
		if (!root->right)
			return minDepth(root->left) + 1;
		return min(minDepth(root->left), minDepth(root->right)) + 1;
	}

	// 112. Check if tree has path sum
	bool hasPathSum(TreeNode *root, int targetSum)
	{
		if (!root)
			return false;

		if (!root->left && !root->right)
			return targetSum == root->val;

		return hasPathSum(root->left, targetSum - root->val) ||
			   hasPathSum(root->right, targetSum - root->val);
	}

	// Preorder traversal helper
	void preorder(TreeNode *root, vector<int> &arr)
	{
		if (!root)
			return;
		arr.push_back(root->val);
		preorder(root->left, arr);
		preorder(root->right, arr);
	}

	// 144. Preorder traversal
	vector<int> preorderTraversal(TreeNode *root)
	{
		vector<int> res;
		if (!root)
			return res;
		preorder(root, res);
		return res;
	}

	// Postorder traversal helper
	void postorder(TreeNode *root, vector<int> &arr)
	{
		if (!root)
			return;
		postorder(root->left, arr);
		postorder(root->right, arr);
		arr.push_back(root->val);
	}

	// 145. Postorder traversal
	vector<int> postorderTraversal(TreeNode *root)
	{
		vector<int> res;
		if (!root)
			return res;
		postorder(root, res);
		return res;
	}

	// 222. Count nodes (BFS)
	int countNodes(TreeNode *root)
	{
		if (!root)
			return 0;

		queue<TreeNode *> q;
		q.push(root);

		TreeNode *cur;
		int res = 0;
		while (!q.empty())
		{
			cur = q.front();
			q.pop();
			res++;

			if (cur->left)
				q.push(cur->left);
			if (cur->right)
				q.push(cur->right);
		}
		return res;
	}

	// 222. Count nodes optimized for complete tree
	int getHeight(TreeNode *root)
	{
		int h = 0;
		while (root)
		{
			h++;
			root = root->left;
		}
		return h;
	}

	int countNodes(TreeNode *root)
	{
		if (!root)
			return 0;

		int leftHeight = getHeight(root->left);
		int rightHeight = getHeight(root->right);

		if (leftHeight == rightHeight)
			return (1 << leftHeight) + countNodes(root->right);
		else
			return (1 << rightHeight) + countNodes(root->left);
	}

	// 226. Invert binary tree
	TreeNode *invertTree(TreeNode *root)
	{
		if (!root)
			return NULL;

		TreeNode *cur = invertTree(root->right);
		root->right = invertTree(root->left);
		root->left = cur;

		return root;
	}

	// DFS helper for paths
	void dfs(TreeNode *root, vector<string> &arr, string cur)
	{
		if (!root)
			return;

		if (!cur.empty())
			cur += "->";
		cur += to_string(root->val);

		if (!root->left && !root->right)
		{
			arr.push_back(cur);
			return;
		}

		if (root->left)
			dfs(root->left, arr, cur);
		if (root->right)
			dfs(root->right, arr, cur);
	}

	// 257. Binary tree paths
	vector<string> binaryTreePaths(TreeNode *root)
	{
		vector<string> res;
		dfs(root, res, "");
		return res;
	}

	// 404. Sum of left leaves
	int sumOfLeftLeaves(TreeNode *root)
	{
		if (!root)
			return 0;
		queue<TreeNode *> q;
		q.push(root);
		TreeNode *cur;
		int res = 0;
		while (!q.empty())
		{
			cur = q.front();
			q.pop();
			if (cur->left)
			{
				if (!cur->left->left && !cur->left->right)
					res += cur->left->val;

				q.push(cur->left);
			}
			if (cur->right)
				q.push(cur->right);
		}
		return res;
	}

	// 501. Find mode in BST
	vector<int> findMode(TreeNode *root)
	{
		queue<TreeNode *> q;
		q.push(root);

		unordered_map<int, int> map;
		TreeNode *cur;
		while (!q.empty())
		{
			cur = q.front();
			q.pop();
			map[cur->val]++;

			if (cur->left)
				q.push(cur->left);
			if (cur->right)
				q.push(cur->right);
		}

		int maxCount = 0;
		for (auto &x : map)
		{
			maxCount = max(maxCount, x.second);
		}

		vector<int> res;
		for (auto &x : map)
		{
			if (x.second == maxCount)
			{
				res.push_back(x.first);
			}
		}

		return res;
	}

	// 530. Minimum difference in BST
	int getMinimumDifference(TreeNode *root)
	{
		queue<TreeNode *> q;
		q.push(root);
		TreeNode *cur = root;
		vector<int> arr;
		while (!q.empty())
		{
			cur = q.front();
			q.pop();
			arr.push_back(cur->val);

			if (cur->left)
				q.push(cur->left);
			if (cur->right)
				q.push(cur->right);
		}

		int res = INT_MAX;
		sort(arr.begin(), arr.end());
		for (int i = 0; i < arr.size() - 1; i++)
		{
			res = min(res, arr[i + 1] - arr[i]);
		}
		return res;
	}

	// 543. Diameter of binary tree
	int res = 0;
	int height(TreeNode *root)
	{
		if (!root)
			return 0;

		int left = height(root->left);
		int right = height(root->right);

		res = max(res, left + right);

		return max(left, right) + 1;
	}

	int diameterOfBinaryTree(TreeNode *root)
	{
		height(root);
		return res;
	}

	// 563. Find tilt of binary tree
	int sumNode(TreeNode *root)
	{
		if (!root)
			return 0;
		int left = sumNode(root->left);
		int right = sumNode(root->right);
		res += abs(left - right);
		return left + right + root->val;
	}

	int findTilt(TreeNode *root)
	{
		int nodes = sumNode(root);
		return res;
	}

	// 572. Check if subtree
	bool isSubtree(TreeNode *root, TreeNode *subRoot)
	{
		if (!root)
			return false;
		if (isSameTree(root, subRoot))
			return true;
		return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
	}
};
